For 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 (4)

1
vote
0answers
23 views

Is there a name for the relationship between matching combinations?

Is there a term that describes the relationship between $\binom 3 1 = \binom 3 2$ or $\binom 5 2 = \binom 5 3$? Symmetric comes to mind, but I was wondering if a specific term is used to describe ...
2
votes
1answer
33 views

Counting the functions with f(i) ≤ f(i+1) for all i=1,..,n-1

How can I determine how many functions are weakly monotone increasing from $[n]\equiv \{1,..,n\}$ to itself: $$ f:[n] \to [n] \text{ so that } f(i) \leq f(i+1) \; \forall i\in[n-1]$$ Thank you for ...
1
vote
1answer
21 views

A conjecture on binomial factors

Can any one help me prove the following conjecture: \begin{equation} \sum_{p=1}^{\min(n,m+1)}C_{m+1}^p C_{n-1}^{p-1}=\sum_{p=1}^{\min(m+1,n+1)}C_n^{p-1}C_m^{p-1}=C_{m+n}^n \end{equation} Here ...
0
votes
1answer
333 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
1
vote
0answers
45 views

Partitioning real numbers with sum $1$ to sets

If the sum of a finite number of positive real numbers is $1$ and each of them is less than $x$, then those real numbers can be partitioned into $50$ sets (some of which may be empty) such that the ...
3
votes
2answers
81 views

Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong. Let $G$ be a large directioned ...
1
vote
1answer
30 views

How many different towers, with regards to colour, can be built?

You are going to build a tower with coloured blocks. There are ten available blocks, of which three are white, two are red, two are yellow, one is green, one is blue and one is black. The tower you ...
2
votes
2answers
31 views

Number of ways to place $K$ objects in $N^3$ cube

On how many ways I can place $K$ objects in $N \times N \times N$ cube, assuming that in every coordinate $x$, $y$, $z$ (i.e. in every "row") may be at most one object? For example, if $N = 2$ and $K ...
0
votes
1answer
13 views

Which is the more likely outcome when dealing cards.

Suppose you are given 6 cards. Which is more likely, you get $3$ different value cards with value having $2$ suits. (e.g. two aces two kings and two jacks). Or $2$ different value cards with $3$ ...
1
vote
2answers
32 views

How many 3 letters-long codes can be made by 5 different letters?

You have five letters: C, H, E, S, T How many different codes, consisting of three letters, can be made from the above letters? I'd say ${5}\choose{3}$ is the correct answer, since the order of the ...
5
votes
5answers
641 views

Given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
2
votes
1answer
292 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
0
votes
2answers
31 views

Number of ways to assign $8$ subjects to $4$ people s.t. one gets an odd number of subjects

I am asked to find the number of ways to assign $8$ subjects to $4$ people, such that the third person always gets an odd number of subjects. What I did was consider the problem as putting ...
2
votes
0answers
46 views

Different coloured bottles of two different sizes

Question The table below shows the distribution by colour (green, blue and red) and size (small and large) of a collection of $20$ bottles. All other features of the bottles are exactly the same. ...
0
votes
0answers
26 views

Sum of products of K numbers taken from N numbers in closed form

Let's say i have 5 numbers, $A,B,C,D,E$. I want to know the sum of all the possible products of some or all of these numbers each taken at most once. Instead of a lot of multiplications and additions ...
4
votes
1answer
268 views

a combinatorial exercise

The problem asks us to calculate: $$ \sum_{i = 0}^{n}(-1)^i \binom{n}{i} \binom{n}{n-i}$$ The way I tried solving is: The given sum is the coefficient of $x^n$ in $ (1+x)^n(1-x)^n $, which is $ (1 ...
2
votes
1answer
44 views

What do we call well-founded posets whose elements have a unique height?

What do we call those well-founded posets $P$ with the property that for every $x \in P$, all maximal chains in the lowerset generated by $x$ have the same length? Examples: The set of all finite ...
0
votes
3answers
50 views

How to approach combinatorics proofs like these.

Okay so I have been trying to solve problems for my course and keep running into persistent issues with proofs. For example. Prove the following: $${n\choose r}={n-1\choose r-1}+{n-1\choose r}$$ ...
0
votes
0answers
16 views

Enumerating set combinations in an order that maximises the number of previously unseen subsets

Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$. There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$. There are $462! \approx 1.419 × 10^{1032}$ possible ...
1
vote
1answer
35 views

How many $n$ x $n$ matrices with this given property?

I would like to know how many $n$ x $n$ matrices are there containing elements that are either $1$ or $-1$, such that the product of the elements in each row and column is $-1$?
4
votes
1answer
79 views

How many $s,t,u$ satisfy: $s +2t+3u +\ldots = n$?

Given $n\in \mathbb{N}^+$, what is the possible number of combinations $s,t,u,\ldots\in\mathbb{N}$, such that: $$s +2t+3u +\ldots = n\quad?$$ Additionally, is there an efficient way to find ...
15
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
1
vote
1answer
54 views

The numbers of functions : There are not exist $f(i) < f(i+1) <f(i+2)$

I solved this problem some days ago. Find the numbers of functions $f$ that satisfy these three conditions: (1) $f$ is a bijection (2) $f : \{1, 2, 3,4\} \to \{1, 2, 3,4\}$ (3)We do not ...
0
votes
3answers
38 views

Questions about Two Identities in Derangements

I found in Wiki following identities. I think these are very nice. But I don't know how prove these identities. $!n = \left[\dfrac{n!}{e}\right] = \left\lfloor \dfrac{n!}{e} + ...
1
vote
1answer
52 views

transforming ordinary generating function into exponential generating function

I have seen a post here that says that you can convert an exponential generating function into an ordinary one with the aid of the Laplace transform. Is it possible to do the reverse transformation? ...
1
vote
0answers
28 views

Cardinality of a set of permutations of integers mod $p$.

Let $p$ be a prime number. I wonder if there is a closed formula for the number of permutations $\sigma$ of $ \{0,1,\ldots ,p-1\}$ such that $$\sum_x x \cdot \sigma(x) \equiv 0 \mod p$$ Obs: The ...
0
votes
0answers
11 views

How big can a $k$-sum free set be?

Let $S \subset [1, \dots, n]$. Say that $S$ is $k$-sum free if, for any $\{z_i\} \in \mathbb{Z}$ such that this equation holds: $z_1 s_1 + \dots + z_{|S|}s_{|S|} = 0$ we have $|z_1| + \dots + ...
0
votes
2answers
30 views

How to show $x,y,z \in A$ - Functions, Combinatorics

If $A \subseteq \{1,2,3,4,5,6\}$, how to show that for every $A$ there are $x,y,z \in \{1,2,3,4,5,6\}$, where $x,y,z$ can also be the same or at least not different from each other, and the following ...
2
votes
1answer
43 views

Proving $R(3,4)\le 9$

I am trying to prove $R(3,4)\le 9$. This is my approach: For any $K_9$ we have (WLOG) at least 4 red edges by the pigeonhole principle. Consider all of the edges between these 4 red edges, if ...
3
votes
1answer
85 views

Power series as fractions

This is what I did: \begin{equation*} (x^3-x^6)x^6[x+x^2+x^3+..], \\ \frac{(x^3-x^6)x^6}{1-x}. \end{equation*} What mistake did I make? And, How to solve this: $1+3x^2+9x^4+27x^6+...+3^{157}x^{314}$ ...
1
vote
2answers
189 views

Probability of drawing a pair from a poker hand, unordered with replacement?

I am wondering what is the probability with which you can draw a pair in a 5-card hand from a standard 52-card deck, if order does not matter in the context of cards in the hand, and if the cards can ...
0
votes
1answer
23 views

How many ways there are to arrange a boolean $2\times5$ matrix such that there won't be two zeros one above the other

How many ways there are to arrange a boolean $2\times5$ matrix such that there won't be two zeros one above the other. For example, this is not allowed ...
2
votes
1answer
31 views

Questions on integer-valued polynomials

An integer-valued polynomial or numerical polynomial is a polynomial $f \in \mathbb Q[x]$ with the property that $f(\mathbb Z)\subseteq \mathbb Z$. The set of numerical polynomials forms a subring ...
3
votes
1answer
55 views

Game with stones

Alice and Bob are playing a game. There is a pile of 2014 stones. Alice and Bob alternate taking stones from the pile, with Alice going fi rst. The number of stones Alice takes must be a power of 2 ...
6
votes
0answers
87 views

How many ways are there to fill up a $2n \times 2n$ matrix with $1, -1$?

How many ways are there to fill up a $2n \times 2n$ matrix with $1, -1$ so that each column and each row has exactly $n $ $1$'s and $n$ $-1$'s ? I tried for cases $n=1 , 2$ but the solutions were ...
7
votes
1answer
223 views

Combinatorial Interpretation of Graph Theoretical Relation Involving Chebyshev Polynomials

Given a graph $G$ and its adjacency matrix $A$. The $(i,j)$-th element of $A^r$ gives the number of ways to get from vertex $i$ to $j$ in $r$ steps (including backtracking). Now, the number of ...
4
votes
3answers
54 views

Proving that $r{n \choose r}=n{n-1\choose r-1}$

For proving that: $r{n \choose r}=n{n-1\choose r-1}$ I attempted it with: $r{n\choose r}=\frac{rn!}{r!(n-r)!}=\frac{n!}{(r-1)!(n-r)!}$ $n{n-1\choose ...
2
votes
2answers
35 views

Drawing colored balls

I have a sack with $15$ red balls, $15$ blue balls, $15$ green balls and $15$ yellow balls (balls of the same color are indistingishable). In how many ways can I take $30$ balls from the sack? $\\ ...
1
vote
1answer
21 views

Quick question for proof on unimodal sequence formula in Enumerative Combinatorics

I am looking at page 238 of Stanley's Enumerative Combinatorics where he says that $\#V_n = \#D_n - \#V_n^1$ because every element in $V_n^1$ appears twice as a value of $\Gamma_1$. Can someone ...
3
votes
2answers
88 views

Formal power series coefficient problem

Find the coefficient of: $[x^{33}](x+x^3)(1+5x^6)^{-13}(1-8x^9)^{-37}$ I have figured out that I need to use this identity: $(1-x)^{-k} = \sum\limits_{i>=0} \binom {n+k-1} {k-1} x^n $ But I ...
2
votes
2answers
46 views

Prove this binomial identity using induction

prove this identity: $(1-x)^{-k} = \sum\limits_{i>=0} \binom {n+k-1} {k-1} x^n $ using induction. Verification for k=1 is trivial. assuming k= i, proving the identity when k=i+1 is something i ...
4
votes
2answers
86 views

A fair die is rolled n times. What is the probability that at least 1 of the 6 values never appears?

A fair die is rolled $n$ times. What is the probability that at least 1 of the 6 values never appears? I went about calculating the complement of this, because it seemed to be easier. However, I am ...
0
votes
1answer
61 views

A recurrence for a combinatorial problem

$N$ balls are tossed into $n$ boxes independently. Each ball has a $1/n$ chance of falling into any box.$$P_{N,n}(k):= Pr\{exactly\:k\:empty\:boxes\:after\:N\:balls\:thrown\:into\:n\:boxes\}$$ Show ...
4
votes
1answer
80 views

Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n). The restriction on the first type of bit string is that they must have the same ...
0
votes
1answer
291 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
1answer
22 views

proof for Erdős-Szekeres theorem using Dilworth's theorem

Let's review a few definitions: Dilwoths's theorem: Suppose that the length of the longest antichain in the poset $P$ is $r$, then $P$ can be partitioned into $r$ chains. Dilworth's dual theorem: ...
2
votes
0answers
46 views

How many possible six-word sentences

A word is defined as a nonempty (possibly meaningless) sequence of letters. How many $6$-word sentences can be made using each of the $26$ letters of the alphabet exactly once? Generalise the result ...
-1
votes
1answer
30 views

Number of ways to pick $K$ balls? [closed]

Given $M$ type of balls, and for each type there are $N$ unique balls(means all balls of same type are labeled). In how many ways can we pick up $K$ balls out of these $N*M$ balls such that atleast ...
0
votes
0answers
10 views

Existence of two-color paths between boundary vertices in a near-triangulated plane graph with an external face of degree 4

Let G be a plane graph with the following characteristics: It is near-triangulated. It has an external face of degree 4 (i.e. the graph has 4 boundary vertices, a diamond-shaped boundary ring). It ...
0
votes
2answers
41 views

Trying to determine the number of possible combinations for a password

OVERVIEW: Making a secure password. People tend to use dictionary words as a basis for their passwords. People tend to make minor substitutions on their passwords (password -> p@$$w0rd) Assuming ...