This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

0
votes
1answer
44 views

The existence of two couples of dancers that did not exchange partners

At a homecoming dance, no boy dances with every girl, but each girl dances with at least one boy. Prove that there are two couples, gb and g'b', who dance, such that g doesn't dance with b' and g' ...
0
votes
1answer
8 views

Evaluating the $L_2[-1, 1]$ inner product on rescaled Legendre polynomials

Let $z_n(t) = \sqrt{\frac{2n+1}{2}} \frac{1}{2^n n!} \frac {d^n}{dt^n} (t^2-1)^n$, a rescaled Legendre polynomial. As an intermediate step of a larger problem, I need to show that in terms of the ...
0
votes
3answers
33 views

Combinatorial - how many ways to divide objects into two groups

As a part of a bigger problem I have to determine In how many ways $37$ different objects can be divided among two groups of $32$ and $5$ objects each if i) object $A$ and $B$ cannot belong to the ...
3
votes
0answers
22 views

Bound on number of breakable sets

Let $\mathcal{S}$ be a finite family of finite sets. A finite set $A$ is called breakable if for every $B\subseteq A$, there exists $S\in \mathcal{S}$ such that $A\cap S=B$. Show that at least ...
0
votes
1answer
56 views

how many people are at the party

At a party, each person shakes hands with 5 other people. There are a total of 60 handshakes. How many people are at the party? i am lost because of the 60 hand shake that is mentioned.
1
vote
3answers
64 views

Show that a set of vectors is linearly dependent

Show that the set $S = \{(3, 2), (−1, 1), (4, 0)\}$ is linearly dependent by finding a nontrivial linear combination of vectors in the set whose sum is the zero vector. (Use $s_1$, $s_2$, and ...
0
votes
0answers
19 views

Calculate sum of distinct pairs [closed]

Given an array A we need to find the sum of all distinct pairs of indexes from the array and adds the value ⌊$A[i]+A[j]\over A[i]×A[j]$⌋ to the sum Note: ⌊$A\over B$⌋ is the integer division ...
0
votes
1answer
22 views

Distributing different things into groups

How to distribute four different things in two groups.. Actual question was you have four different types of animals a wolf, a monkey, a tiger and a lion and you have two cages. Find No. Of ways of ...
0
votes
0answers
8 views

How many distinct partials of order $k$ for a function $f: \mathbb{R}^{n}\rightarrow\mathbb{R}$?

Studying for the math subject GRE, and I come across the titular question. I didn't take any combinatorics or probability courses in college, and I'm realizing I have no intuition for counting. Could ...
1
vote
0answers
21 views

Counting similar pairs

I was given a simple programming assignment: Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are ...
0
votes
0answers
41 views

Colorings of squares divided into four colored triangles

You have to form a square by combining four isosceles right triangles of various colors, as in FIGURE shown below. Two squares are considered equally colorful if you can arrange so that the ...
0
votes
1answer
16 views

permutations combinations

Q1. Total number of permutations of k diferent things , in a row , taken not more than r at a time(each thing may be repeated any no. of times) is equal to Q2. A teacher takes 3 children from her ...
0
votes
1answer
48 views

combinatorics- persons in group

Let $$ n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2 $$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each ...
0
votes
4answers
45 views

Simple Combination Help! [closed]

Alright, I'm trying to do a simple combination but seem to forget the shortcut. It is (c(6,2)+c(4,2)) over c(10,2). Now finding the answer on my calculator is easy, the problem is that I need to know ...
1
vote
0answers
11 views

How to generate list of values that sum to X given n spots where each value is unique.

For example: Given 2 spots and sum 3 the list would be {1,2} Given 2 spots and sum 4 list would be {1,3} does not contain 2 as putting 2 in both spots violates the uniqueness of each value.
5
votes
1answer
65 views

Toss a fair die until the cumulative sum is a perfect square-Expected Value

Suppose we keep tossing a fair dice until we want to stop, at which point the game ends and our score is the cumulative sum, or until the cumulative sum is a perfect square, in which case we lose and ...
0
votes
1answer
45 views

Proof involving k-permutations

For any nonnegative integers k and m satisfying $0 ≤ k ≤ m$, prove that the total number of $k$-permutations of a set of m elements is $\frac{m!}{(m − k)!}$. I have learned about by proofs by strong ...
1
vote
0answers
24 views

Time for all ants to traverse cube

Let $n$ be a positive integer, and consider a hypercube of dimension $2n$ with $2^{2n}$ points given by $(a_1,a_2,\ldots,a_{2n})$, where $a_i\in\{0,1\}$. At the beginning, an ant is at each of the ...
1
vote
0answers
25 views

the probability of existence sequence [on hold]

We have n fruit that they are apple or banana. If the probability of existence apple in a specific sequence be p. What is the probability of existence a sequence of k apple in that specific sequence?
1
vote
1answer
26 views

How to generate a single instance of multichoose (stars and bars)

So we know that if I have $k$ balls and $n$ buckets, I have $\binom{n+k-1}{k}$ unique ways to allocate the balls. Let's say $n=4$ and $k=2$ then I have $\binom{5}{2}=10$ ways. All possible allocations ...
-1
votes
1answer
23 views

tasks with balls and buckets

We have p identical balls and buckets. We want to know how many ways we can deploy in these buckets. Is my solution good? Why not, why yes (please confirm)? $$ \frac {w ^ p} {p!}$$ For each ball ...
0
votes
1answer
87 views

Probability in DNA segmentation

I have formulated these questions ss part of a research in medical science (DNA segmentation): A series of $M$ identical balls is arranged on a line. A partition is formed by placing a stick to ...
-5
votes
1answer
122 views

Pixel Permutations

How many possible arrangements of pixels can a 1024x768 pixel screen display if the color of a pixel is determined by mixing 3 values: red, green, and blue, ranging from an intensity of 0 to 255? The ...
4
votes
1answer
62 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
1
vote
0answers
35 views
+50

Aumann-Shapley Uniformly Better Principle

Let $n_1,..,n_r$ be $r$ positive integers, and let $1 \leq k \leq n$, where $n=n_1+...+n_r$. Consider an urn containing $r$ different types of balls, $n_1$ balls of type 1, $n_2$ balls of type ...
0
votes
0answers
14 views

Number of ways to transform bit string of length k with j ones

Suppose we can transform any bit string $s$ of length $k$ with $j$ 1s by moving every 1 in $s$ by at most $d$ positions to the right. The resulting string $s'$ is a string of length $k+d$ where every ...
0
votes
2answers
52 views

Probability that at least 1 of the 3 bridge hands is void of clubs given… [closed]

A bridge hand is dealt so each of 4 players has 13 cards from the 52 card deck. You have 8 clubs in your hand. What is the probability that at least one of the other three hands is void in clubs?
0
votes
1answer
40 views

Decorate Tables

You have $r$ red, $g$ green and $b$ blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What ...
0
votes
0answers
18 views

Combinatoric task with piggy-bank

Every day king puts either 1p or 2p into a piggy-bank and the total is m pence after n days. Show that for any integer k with 0 <= k <= 2n-m there will have been a period of consecutive days ...
0
votes
0answers
29 views

Modified Graph Coloring Problem

Imagine I have a graph that I'm trying to color with two colors, white and black, except unlike the normal graph coloring problem where you say no two vertices of the same color can be adjacent, I ...
0
votes
1answer
38 views

Finding next permutation of a number.

I need to code some problem and I need help permutating the numbers. The problem is: Given a permutation of the numbers $1,2,3,\ldots,n$ e.g. $n=5$ and permutation is $43251$. I need to find the ...
2
votes
1answer
81 views

Number of possible permutations of n1 1's, n2 2's, n3 3's, n4 4's such that no two adjacent elements are same?

Given n1 number of 1's, n2 number of 2's, n3 number of 3's, n4 number of 4's. form a sequence using all these numbers such that two adjacent numbers should not be same. I have tries lot of things ...
0
votes
0answers
21 views

Sum of two sets with combination

I'm a beginner in mathematics, so, I may be confusing with the vectors... Is there a name and definite operator for this operation ? Two sets A and B : $$A = \{ a_0, a_1 \} \\ B = \{ b_0, b_1, b_2 ...
0
votes
1answer
17 views

number of functions from one set to the other

Let $f:\{0,1,2\}→\{1,2,3,4,5,6,7\}$ be a function such that for every $i, \, j\in {\{0,1,2\}}$ where $i<j$, we have $f(i)<f(j)$. How many such functions can we have? Taking different cases for ...
1
vote
3answers
36 views

Probability of drawing certain hand, incorrect answer, but why? [duplicate]

So I am drawing $5$ cards from a standard deck of $52%$ I want to find the probability that I draw $5$ consecutive cards of same suit with no card looping, and the ace is card $1$. So the ...
2
votes
2answers
26 views

Counting Number of Possibilities using Inclusion-Exclusion

I have been tasked with answering the following combinatorics problem for a homework assignment: Consider the set of all six digit numbers that don’t begin with 0. How many of these have at least one ...
1
vote
0answers
22 views

How many Mad Libs combinations will result when requiring a particular distance between sentences?

You are randomly filling in a Mad Libs type sentence with words from a set of dictionaries. For instance: Sentence: The [COLOR] [ANIMAL] [VERBED] a [NOUN]. Dictionaries: COLOR: blue white orange ...
1
vote
3answers
53 views

Prove $n^{n+1}$ is greater than $(n+1)^n$ for all $n > 2$

The question of whether $2014^{2015}$ or $2015^{2014}$ is greater came up in my Calculus class and it seems clear that $2014^{2015} > 2015^{2014}$ based on a table comparing the sequences $s_n = ...
1
vote
0answers
17 views

How can you tile this checkerboard with trominoes? [duplicate]

Ok, so define a tromino as a $1$x$3$ tile. If a corner is removed from an $8$x$8$ board, is it possible to tile it with these trominoes? So far, I have concluded that you would need $21$ trominoes to ...
1
vote
1answer
43 views

Counting Problems

a) A set of eight tiles can be arranged to form the word SATURDAY. How many three-letter “words” can be formed with these tiles if no tile is to be used more than once? I did $8\cdot 7\cdot 6$ but ...
1
vote
0answers
71 views

Calculating the probability of letter assignment

We have 10 letters written to 10 different friends and the 10 addressed envelops. The letters are put into the envelops at random, that is, all 10! assignment are equally likely. (a) What is the ...
2
votes
1answer
29 views

How many ways to place n distingusishable balls into m distinguishable bins of size s?

Let there be $n$ distinguishable balls and $m$ distinguishable bins, each bin of size $s$, that is, we cannot place more than $s$ balls into it. How many possibilites are there to place the balls into ...
0
votes
1answer
16 views

Finding a seating arrangement of $4$ different people in $n$ rounds

I have a practical problem. I want to arrange a speeddate event with $24$ or $32$ people in $7$ rounds. I have a room with sufficiently many tables and I want $4$ people per table and each round must ...
1
vote
0answers
40 views

Counting the number of partitions having blocks of cardinality 2 and non-distinct elements

Say I have a set of integers $\{1,2,\cdots,n\}$, then there exists $B_n$ partitions of this set where $B_n$ is a Bell number. For instance, there are $B_3$=5 partitions of the set $\{1,2,3\}$: $$ ...
1
vote
0answers
25 views

Upper bound on number of ways to place $n$ indistinguishable objects into $k$ distinguishable intervals of size $s$

I need a simple, but tight upper bound on the number of ways to distribute some $n$ indistinguishable objects among $k$ distinguishable boxes of size $s$. The formula for this quantity is absolutely ...
-1
votes
0answers
12 views

Birkhoff polytope (diameter is $2$)

I did not understand the proof of the following proposition: Prop. $2.29$: Diameter of birkhoff polytope is $2$. This is the link.
0
votes
0answers
11 views

Hyperplane arrangements and matroids

I'm studying some topics related to hyperplane arrangements and matroids. I've some problem in finding some practical example. Here's my question: Let $\mathbb{K}$ be a field (suppose of ...
0
votes
1answer
61 views

How many 6 digit numbers with 2 or 3 repetitions allowed

Solution is pretty well known for the question: how many $6$ digit numbers can be written by using digits $0,..,9$, where, every digit can be used only once. However, while I was thinking today, I ...
3
votes
1answer
49 views

Combinatorics in chess

Let $ ABCD \ $ be an finite chessboard ($n*n$ tiles) where $A$ is the left lower corner and $C$ its opposite. Each tile is denoted by a square with length $L=1$. Our purpose is to determine the ...
0
votes
1answer
13 views

Problem finding $10$-combinations of multisets

Today I had my exam of discrete maths and was asked to find the: no. of $10$-combinations of multiset $\{\infty a,3b,6c\}$. What I did was that: consider set $A_1=$ no. of ways such that no ...